package com.yubest;

/**
 * 给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
 *
 * 对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
 *
 * 返回这些数字之和。题目数据保证答案是一个 32 位 整数。
 *
 *  
 *
 * 示例 1：[图片] img/1022.png
 *
 *
 * 输入：root = [1,0,1,0,1,0,1]
 * 输出：22
 * 解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
 * 示例 2：
 *
 * 输入：root = [0]
 * 输出：0
 * 示例 3：
 *
 * 输入：root = [1]
 * 输出：1
 * 示例 4：
 *
 * 输入：root = [1,1]
 * 输出：3
 *  
 *
 * 提示：
 *
 * 树中的结点数介于 1 和 1000 之间。
 * Node.val 为 0 或 1 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sum-of-root-to-leaf-binary-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/12 16:29
 */
public class P1022 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(0), new TreeNode(1));
        new Solution1022().sumRootToLeaf(root);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution1022 {

    /**
     * 思路：计算出所有的组合，然后累计值
     * @param root
     * @return
     */
//    public int sumRootToLeaf(TreeNode root) {
//        List<String> result = new ArrayList<>();
//        dfs(root, "", result);
//        int total = 0;
//        for (String s : result) {
//            total += Integer.valueOf(s, 2);
//        }
//        return total;
//    }
//
//    private void dfs(TreeNode node, String prefix, List<String> result) {
//        if (null == node) {
//            return;
//        }
//        prefix += node.val;
//        if (null == node.left && null == node.right) {
//            result.add(prefix);
//        }
//        dfs(node.left, prefix, result);
//        dfs(node.right, prefix, result);
//    }

    private int total = 0;

    /**
     * 思路：用一个变量维护到达当前节点时所记录的十进制数，如果该节点是叶子节点，加入答案。
     */
    public int sumRootToLeaf(TreeNode root) {
        dfs(root, 0);
        return total;
    }

    private void dfs(TreeNode node, int curTotal) {
        if (null == node) {
            return;
        }
        //计算curTotal
        curTotal = (curTotal << 1) + node.val;
        if (null == node.left && null == node.right) {
            total += curTotal;
        }
        dfs(node.left, curTotal);
        dfs(node.right, curTotal);
    }

}
